package 送货;

import java.util.Arrays;
import java.util.Scanner;

/**
 * <p>
 * Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次
 * <p>
 * 优化时考虑：
 * 1.哪些点被用过
 * 2.当前在哪个点
 * <p>
 * 集合：从0走到j，走过的点是i的集合的所有路径
 * 属性：min
 * 集合的划分：0走到j之前有一点k(0->k->j),以k为终点的最短距离
 * 用n位二进制数来表示i的点集：1表示经过了这个点，0表示未经过这个点
 * dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+w[k][j])
 */
public class shortestHamiltonPath {
    static int N = 20, M = 1 << N,INF = 9999;
    static int[][] dp = new int[M][N];
    //ad是有N个点的无向图的邻接矩阵
    static int[][] ad = new int[N][N];
    static int n,m;
    static Scanner sc = new Scanner(System.in);

    static void chooseM(){
        System.out.println("请选择输入模式：");
        System.out.println("模式1：点点边");
        System.out.println("模式2：直接输入邻接矩阵");
        int choose = sc.nextInt();
        switch (choose){
            default:
                System.out.println("无此功能");
                break;
            case 1:
                inputEdge();
                break;
            case 2:
                inputAd();
                break;
        }
    }
    static void inputEdge(){
        System.out.println("请输入点和边的数量 和边：");
         n = sc.nextInt();
         m = sc.nextInt();
        ad = new int[n+1][n+1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    ad[i][j] = 0;
                } else {
                    ad[i][j] = INF;
                }
            }
        }
        while (m-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            ad[a-1][b-1] = Math.min(ad[a-1][b-1], c);
//----------------有向图---------------
            ad[b-1][a-1]= ad[a-1][b-1];
//-------------------------------------------------
        }
    }
    static void inputAd(){
        System.out.println("请输入点数和邻接矩阵");
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ad[i][j] = sc.nextInt();
            }
        }
    }
    public static void main(String[] args) {
        chooseM();

        int range = 1 << n;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = INF;
            }
        }
        //起点是0
        dp[1][0] = 0;
        for (int i = 0; i < range; i++) {
            for (int j = 0; j < n; j++) {
                //i >> j & 1,判断i的二进制的第j位
                if ((i >> j & 1) != 0) {
                    for (int k = 0; k < n; k++) {
                        if ((i>>k&1)!=0){
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + ad[j][k]);
                        }
                    }
                }
            }
        }
//        for (int []i:ad){
//            System.out.println(Arrays.toString(i)   );
//        }
//        for(int i = 0; i <(1 << n); i++) {
//            for(int j = 0; j <n; j++) {
//                System.out.print(dp[i][j]+ " ");
//            }
//            System.out.println();
//        }
        if (dp[(1 << n) - 1][n - 1]==INF){
            System.out.println("存在不连通");
        }else {
            System.out.println("走过所有点到终点且最短的路径为"+ dp[(1 << n) - 1][n - 1]);

        }
    }
}
